Conventionally, in a multi-character (networked) game, characters may interact in the same instance of the game. Users or players may interact with non-player characters (NPC), typically controlled through Artificial Intelligence (AI). NPCs actions and movements may be governed by the same or similar rules (e.g. physics rules) as characters controlled by human players. For example, characters may be not permitted to walk through walls or other types of non-traversable objects. The terms traversable and navigable may be used interchangeably herein.
Typically, the map of the virtual space is similar if not the same for all players. That is, the terrain is mostly the same, even if some smaller objects may be in different locations for different players. Some games allow a player to design his own terrain prior to engaging other characters interactively. For example, a player may design a battlefield, usually in a separate mode of operation that is different from interactive gameplay.
One way to guide characters through a virtual space may be by constantly checking and/or detecting whether an individual character collides with another character or an object of the type that the individual character is not permitted to traverse. Computationally, collision detection may be costly. As a result, techniques that reduce the need for collision detection may be desirable. For complex virtual spaces that include many objects and many characters, collision detection may be cost-prohibitive, at least unless all or most of the terrain in the virtual space remains fixed in place, having unchanging properties with regard to traversability.